#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>

#define OVERFLOW -1
#define STACKSIZE 100
#define NODESIZE 1000

struct binnode
{
	struct binnode *lchild;	//指向左孩子结点
	struct binnode *rchild;	//指向右孩子结点
	struct binnode *parent;	//指向父节点

	void *pdata;	//该结点的具体信息

	int height;		//该结点作为根的子树高度
};
struct bintree
{
	int size;	//树的规模
	int elemsize;	//每个结点保存的具体信息的结构体的大小 binnode中pdata指向内容的大小
	struct binnode *root;	//根结点
};
struct load_bintree_list
{
	struct binnode *pb;
	struct load_bintree_list *next;
};

struct binnode * createBinnode(struct bintree *tree, void *pdata, struct binnode *parent);	//新建一个结点 它的父结点指向parent 返回值为新建的结点
struct binnode * insertAsLeftChild(struct bintree *tree, void *pdata, struct binnode *parent);
struct binnode * insertAsRightChild(struct bintree *tree, void *pdata, struct binnode *parent);
struct binnode * attachAsLeftChildren(struct bintree *tree, struct binnode * p, struct bintree *subtree);
struct binnode * attachAsRightChildren(struct bintree *tree, struct binnode * p, struct bintree *subtree);

int binnodeSize(struct binnode *p);	//返回p指向结点为根的子树的规模（结点个数）
struct binnode * binnodeSucc(struct binnode *p);	//返回p在中序遍历条件下的直接后继

int updateHeight(struct binnode *p);	//更新结点p的高度
int maxOfTwoInt(int a, int b);
void updateHeightAbove(struct binnode *p);	//更新结点p及其所有父结点的高度


//先序遍历
void preorderTraverse(struct bintree *pb, struct binnode *p, void visit());
void preorderTraverse1(struct bintree *pb, struct binnode *p, void visit());
void visitAlongLeftBranch(struct bintree *pb, struct binnode **pp, void visit(), struct binnode *stack[], int *top);
void preorderTraverse2(struct bintree *pb, struct binnode *p, void visit());

//中序遍历
void inorderTraverse(struct bintree *pb, struct binnode *p, void visit());
void goAlongLeftBranch(struct bintree *pb, struct binnode *p, void visit(), struct binnode *stack[], int *top);
void inorderTraverse1(struct bintree *pb, struct binnode *p, void visit());

//后序遍历
void postorderTraverse(struct bintree *pb, struct binnode *p, void visit());
void gotoHLVFL(struct bintree *pb, struct binnode *stack[], int *top);
void postorderTraverse1(struct bintree *pb, struct binnode *p, void visit());

//层次遍历
void levelTraverse(struct bintree *pb, struct binnode *p, void visit());

void saveOneNodePre(struct bintree *pb, struct binnode *p);
void saveOneNodeIn(struct bintree *pb, struct binnode *p);
void saveBintreeToFile(struct bintree *pb, struct binnode *p);
void loadBintreeFromFile(struct bintree *ptree);


void createATree(struct bintree *tree);
void show_menu(void);
void show_binnode_data(struct bintree *pb, struct binnode *p);


void saveAllNode(struct bintree *pb, struct binnode *p);
void destroyBintree(struct bintree *pt);
struct load_bintree_list * createBintreeFromInorderList(struct bintree *ptree, struct load_bintree_list * pre1, struct load_bintree_list *head, struct load_bintree_list *tail, struct binnode *parent, int left_right);